package com.chengqs.leetcode.hot100;

import com.chengqs.leetcode.utils.DataGeneratorUtil;
import com.chengqs.leetcode.utils.TimeCostUtil;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

/**
 * 子串<br>
 * 哈希表、字符串、滑动窗口<br>
 * 困难
 *
 * <h1>76. 最小覆盖子串</h1>
 *
 * <p>给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。</p>
 */
public class D12MinWindow {
    public static void main(String[] args) {
        D12MinWindow minWindow = new D12MinWindow();

        String s = "ADOBECODEBANC";

        TimeCostUtil.timeCost("滑动窗口", () -> minWindow.solution1(s, "ABC"));
        TimeCostUtil.timeCost("滑动窗口_我的方法", () -> minWindow.solution1_mine(s, "ABC"));

        String str = DataGeneratorUtil.generateRandomString(10000000);
        TimeCostUtil.timeCost("滑动窗口", () -> minWindow.solution1(str, "abcd"));
        TimeCostUtil.timeCost("滑动窗口_我的方法", () -> minWindow.solution1_mine(str, "abcd"));
    }

    public String solution1_mine(String s, String t) {
        if (s == null || t == null || s.length() == 0 || t.length() == 0) {
            return "";
        }

        // 记录 t 中每个字符的出现次数
        Map<Character, Integer> need = new HashMap<>();
        // 记录窗口中每个字符的出现次数
        Map<Character, Integer> window = new HashMap<>();

        // 初始化 need
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        int left = 0, right = 0;
        int valid = 0; // 记录窗口中满足 need 条件的字符个数
        int start = 0; // 最小子串的起始位置
        int minLen = Integer.MAX_VALUE; // 最小子串的长度

        while (right < s.length()) {
            // c 是将移入窗口的字符
            char c = s.charAt(right);
            // 右移窗口
            right++;

            // 进行窗口内数据的一系列更新
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).equals(need.get(c))) {
                    valid++;
                }
            }

            // 判断左侧窗口是否要收缩
            while (valid == need.size()) {
                // 更新最小覆盖子串
                if (right - left < minLen) {
                    start = left;
                    minLen = right - left;
                }

                // d 是将移出窗口的字符
                char d = s.charAt(left);
                // 左移窗口
                left++;

                // 进行窗口内数据的一系列更新
                if (need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d))) {
                        valid--;
                    }
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        // 返回最小覆盖子串
        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }

    Map<Character, Integer> ori = new HashMap<Character, Integer>();
    Map<Character, Integer> cnt = new HashMap<Character, Integer>();

    // 滑动窗口
    public String solution1(String s, String t) {
        int tLen = t.length();
        for (int i = 0; i < tLen; i++) {
            char c = t.charAt(i);
            ori.put(c, ori.getOrDefault(c, 0) + 1);
        }
        int l = 0, r = -1;
        int len = Integer.MAX_VALUE, ansL = -1, ansR = -1;
        int sLen = s.length();
        while (r < sLen) {
            ++r;
            if (r < sLen && ori.containsKey(s.charAt(r))) {
                cnt.put(s.charAt(r), cnt.getOrDefault(s.charAt(r), 0) + 1);
            }
            while (check() && l <= r) {
                if (r - l + 1 < len) {
                    len = r - l + 1;
                    ansL = l;
                    ansR = l + len;
                }
                if (ori.containsKey(s.charAt(l))) {
                    cnt.put(s.charAt(l), cnt.getOrDefault(s.charAt(l), 0) - 1);
                }
                ++l;
            }
        }
        return ansL == -1 ? "" : s.substring(ansL, ansR);
    }

    public boolean check() {
        Iterator iter = ori.entrySet().iterator();
        while (iter.hasNext()) {
            Map.Entry entry = (Map.Entry) iter.next();
            Character key = (Character) entry.getKey();
            Integer val = (Integer) entry.getValue();
            if (cnt.getOrDefault(key, 0) < val) {
                return false;
            }
        }
        return true;
    }
}
